public class Practice1 {

    static int[] tmp;
    public static void mergeSort(int[] nums, int left,int right){
        if(left == right){
            return;
        }
        int mid = (left + right) / 2;
        //[left,mid] [mid + 1, right]
        mergeSort(nums,left,mid);
        mergeSort(nums,mid + 1,right);
        int cur1 = left;
        int cur2 = mid + 1;
        int i = 0;
        while(cur1 <= mid && cur2 <= right){
            if(nums[cur1] > nums[cur2]){
                tmp[i++] = nums[cur2++];
            }else{
                tmp[i++] = nums[cur1++];
            }
        }
        while(cur1 <= mid){
            tmp[i++] = nums[cur1++];
        }

        while(cur2 <= right){
            tmp[i++] = nums[cur2++];
        }

        for(int j = left;j <= right;j++){
            nums[j] = tmp[j - left];
        }
    }

    public static void main(String[] args) {
        int[] nums = {4,65,87,787,8,78,67,6,56,45,43,4,3,43};
        tmp = new int[nums.length];

        mergeSort(nums,0,nums.length - 1);
        System.out.println();
    }
}
